package 动态规划;

import java.util.Arrays;

import org.junit.Test;

public class leetcode组合总和问题最终版本 {
	/**
	 * ①：
	 * 下面的是  可以 重复  选取的  但是 不含 重复 元素 并 全是   正数 
	 * 
	 * 
	 * 
	 * 
	 * 这样写 的 话  对于 数组 是否 有序 就没有  要求 了 但是           无法剪枝
	 * 可能 对于 暴力 递归 来说  肯定会 慢一些 的
	 * 但 对于   记忆化 搜索 和  dp 来说 有没有 影响 呢 
	 * 这是 一个有待商榷的 问题
	 * 两种 都写 一下 ：
	 * 排序 剪枝   ： 记忆化 搜索 和 dp
	 * 不排序   ：     记忆化 搜索 和 dp
	 */
	public static int process(int nums[] ,int rest,int index) {
//		if(rest < 0 || index ==12) {
//			return 0;
//		}
		if(rest == 0) {
			return 1;
		}
		if(rest < 0  || index == nums.length) {
			return 0;
		}
		
		int ways = 0;
		for(int i = index ;i < nums.length;i++) {
			/**
			 * if(rest - nums[i] >= 0)
			 * 在执行 下面的 代码 就可以 之恶极 省去 basecase 中的 rest < 0 的    判断
			 */
			ways += process(nums,rest - nums[i] ,i);
		}
		return ways;
	}
	@Test
	public void test() {
		int choice[] = {7,2,3,5,1};
		int res = process(choice,10,0);
		System.out.println(res);
	}
	
	public static int solution(int nums[],int rest) {
		int len = nums.length;
		int  dp [][] = new int [len + 1][rest + 1];
		for(int i = 0 ; i <= rest; i++) {
			for(int j = 0; j <= len ;j++) {
//				if(i == 0) {
//					dp[j][i] = 1;
//				}
			
					dp[j][i] = -1;
				
			}
		}
		process(nums,rest,0,dp);
		for(int i[] : dp) {
			for(int j : i) {
				System.out.print(j + " ");
			}
			System.out.println();
		}
		return dp[0][rest];
	}
	
	public static int process(int nums[] ,int rest,int index,int dp[][]) {
//		if(rest < 0 || index ==12) {
//			return 0;
//		}
/**
 *  这里 不进行 排序 剪枝 的 话  还暴露  一个 缺点  就是   第一个 basecase  怎么 解决 
 *  根据 之前 写的  经验 来看 这个 basecase 的 值 可以 直接 放在  solution 里面 去做 
 *  在 初始化 数组  中 元素 值 wei -1 的 时候 顺便 把 basecase  也设置一下 
*/
		if(rest < 0  || index == nums.length) {
			return 0;
		}
//		if(rest == 0) {
//			return 1;
//		}
		if(dp[index][rest] != -1) {
			return dp[index][rest];
		}
		if(rest == 0) {
			dp[index][rest] = 1;
			return dp[index][rest];
		}
//		
		int ways = 0;
		for(int i = index ;i < nums.length;i++) {
			ways += process(nums,rest - nums[i] ,i,dp);
		}
		dp[index][rest] = ways; 
		return ways;
	}	
/**
 * 下面这个 是一个 错误的 例子	
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 */
public static int dp (int nums[] ,int target) {	
	  int len = nums.length;
	  int  dp[][]   =  new int [len][target + 1];
	  /**
	   * 初始化 dp  数组 就看  暴力 递归的  basecase 就行
	   */
	  for(int index = len -1;index >= 0;index--) {
		   dp[index][0] = 1;
		  for(int rest = 1; rest <= target; rest++) {
			  int ways = 0;
			  for(int i =index ;i < len && rest - nums[i] >= 0; i++ ) {
				  /**
				   * 注意 这里 和  排序 剪枝 写的 一样   这里 出现 了 一个 新的   疑惑的地方
				   * 
				   * for(int i =index; i < len && rest -nums [i] >= 0; i++)
				   * 
				   * 结果 跟 现在 写的 这种 不一样  ？？？？
				   *    * 解释 ：
				   *如果 for 循环中的  Boolean 表达式 为
				   *false  的 话  那么 直接 结束 for 循环 
				   *这里  有两个  表达式 i < len && rest -nums [i] >= 0
				   *对我造成 了 干扰 我靠 服了 
				   * 
				   * 
				   * 
				   */
//				  if(rest - nums[i] >=0) {
//					  ways += dp[i][rest-nums[i]];
//				  }
				  ways  += dp[i][rest- nums[i]];
			  }
			  dp[index][rest] =ways;
		  }
	  }
	  for(int i []: dp) {
		  for(int j : i) {
			  System.out.print(j + " ");
		  }
		  System.out.println();
	  }
	  return dp[0][target];
}
public static int dpOne (int nums[] ,int target) {	
	  int len = nums.length;
	  int  dp[][]   =  new int [len][target + 1];
	  /**
	   * 初始化 dp  数组 就看  暴力 递归的  basecase 就行
	   */
	  for(int index = len -1;index >= 0;index--) {
		   dp[index][0] = 1;
		  for(int rest = 1; rest <= target; rest++) {
			  int ways = 0;
			  for(int i =index ;i < len; i++ ) {
				  /**
				   * 注意 这里 和  排序 剪枝 写的 一样   这里 出现 了 一个 新的   疑惑的地方
				   * 
				   * for(int i =index; i < len && rest -nums [i] >= 0; i++)
				   * 
				   * 结果 跟 现在 写的 这种 不一样  ？？？？
				   * 
				   * 
				   * 解释 ：
				   *如果 for 循环中的  Boolean 表达式 为
				   *false  的 话  那么 直接 结束 for 循环 
				   *这里  有两个  表达式 i < len && rest -nums [i] >= 0
				   *对我造成 了 干扰 我靠 服了 
				   * 
				   * 
				   * 
				   */
				  if(rest - nums[i] >=0) {
					  ways += dp[i][rest-nums[i]];
				  }
//				  ways  += dp[i][rest- nums[i]];
			  }
			  dp[index][rest] =ways;
		  }
	  }
	  for(int i []: dp) {
		  for(int j : i) {
			  System.out.print(j + " ");
		  }
		  System.out.println();
	  }
	  return dp[0][target];
}
/**
 * 
 * 
 * 存在 枚举 行为 的  暴力 递归 
 * 什么 叫做 存在 枚举  行为 
 * 简单的 来说 就是 
 * 暴力 递归 中 有个 for  循环 这种 
 * 而且 还是  二维 缓存表的 这种形式 （就是  递归 回溯 中 有两个 可变的参数 ）
 * 这种 很大 概率 就是 存在 枚举 行为 
 * 这种 其实 也很 明显 对吧 
 * 就是 写成 dp  之后  有三 层 循环 
 * 这 很大程度 就可以把   内层的for 循环 给优化 掉 
 * 这得 需要 去 尝试 怎么 去  优化 了 
 * 
 * 
 * 终于 他妈的  让我 给 找到 了 这个         最终版本的 dp  
 * 这真的  是 他妈 的 牛逼
 * 
 * 	终于 他妈的  写出来了  
 * @param
 */

public static int dpFinall (int nums[] ,int target) {	
	  int len = nums.length;
	  int  dp[][]   =  new int [len + 1][target + 1];
	  /**
	   * 初始化 dp  数组 就看  暴力 递归的  basecase 就行
	   */
	  for(int index = len -1;index >= 0;index--) {
		   dp[index][0] = 1;
		  for(int rest = 1; rest <= target; rest++) {
			  	dp[index][rest] = dp[index + 1][rest];
			  	if(rest - nums[index] >= 0) {
			  		dp[index][rest] += dp[index][ rest- nums[index]];
			  	}
			  	}
	  }
	  for(int i []: dp) {
		  for(int j : i) {
			  System.out.print(j + " ");
		  }
		  System.out.println();
	  }
	  return dp[0][target];
}


	public static void main(String []args) {
		int candidates []= {1,2,2,3,5,7};
		int target = 10;
//		int candidates[] = {5,10,100,50};
//		int target = 1000;
//		Arrays.sort(candidates);
		System.out.println(process(candidates,target,0));
//		System.out.println(solution(candidates,target));
//		System.out.println(dp(candidates,target));
//		System.out.println(dpOne(candidates,target));
//		System.out.println(dpFinall(candidates,target));
		int arr [] = {2,5,2,1,2};
		int aim = 5;
		Arrays.sort(arr);
		Arrays.sort(candidates);
		int ans = processTwo(candidates,target,0);
		System.out.println(ans);
		System.out.println(dpTwo(candidates,target));
		System.out.println(dpTwoFinall(candidates,target));
		System.out.println(processUpdate(candidates,target,0));
	}
	
	/**
	 * 这里  结合       <射箭比赛的最大得分问题> 去说明 一下 这个问题
	 * 就是 数组 无序的  情况 怎么 去写 这个  逻辑
	 * 注意一下  下面的 代码  rest - nums[i] > 0 这里 进行 剪枝 
	 * 而剪枝  的 前提 就是  对 数组   nums   进行排序才可以 这样 写  
	     for(int i = index ;i < nums.length && rest - nums[i] >= 0;i++) {
		  ways += processTwo(nums,rest - nums[i],i + 1);
	     }
	    
	 但是  如果 题目 中 条件  或者   解答 题目的 过程 中 发现   无法  通过 对数组 排序 而解决 
	 比如 <射箭问题 中的最大得分 >
	 正确 结果 时 对 数组 的 下标 索引 进行 操作 (求和 )
	 那么 排序 后 原先  i 下标  对应的 value 就已经 变了 答案 肯定 是错的   
	 那就 无法 进行 剪枝  操作   那就 直接 算呗
	 
	  那么 对于 该题        <组合 求和>  进行 不剪枝 的操作 示范 
	 
	 * 版本 ② ：
	 * 下面的  是 不可以重复 选取 但是 有 重复  元素 
	 * 这 要 去重的  ；
	 * 去重 的 就 排序 呗 
	 * 并且 排序 之后 就可以 剪枝 了对吧
	 */
	public static int processTwo(int nums[],int rest,int index) { 
		/**
		 * 
		 * 这个 basecase
		 *   还是 加上的 比较  好 因为 这样 可以 
		 *   改 dp  的 时候  会 更轻松 一些 
		 *   不然 就会  像     今天 下面 这个 dpTwo 一样  
		 *   就会出现   数组 越界 和  答案 不一样的  情况 
		 *   第一次 ：
		 *    int  dp [][] = new int [len][target + 1];
		 *   for(int  index = len -1 ; index >= 0;index -- ) {
			dp[index][0] = 1;
			for(int rest = 1; rest <= target;rest++) {
		 *   这样 写 为了 省 一个  int 的 空间 出现 数组越界 
		 *   因为       i+1  的情况 对吧 越界  理所当然
		 *   
		 *   
		 *   
		 *   第二次 ：
		 *   
		 *   int  dp [][] = new int [len + 1][target + 1];
		 *   for(int  index = len; index >= 0;index -- ) {
			dp[index][0] = 1;
			for(int rest = 1; rest <= target;rest++) {
			
			注意 这种写法 就是 
		       index 的范围 是 [0 , len] 所以 这个 index 从 len 开始
		       如果写 index  = len -1  答案 会 不对的 
		       其实 这理解 起来 很正常 啊
		 */
		if(rest == 0){
			return 1;
		}
		/**
		 * 下面的 代码 可以 不写  如果 写的  话 必须 在  
		 * 
		 * 	if(rest == 0){
			return 1;
		}
		 * 的 后面 
		 * 理由的 仔细 观察 就会 发现 
		 * ways += processTwo(nums,rest - nums[i],i + 1);
		 * 当 i+1 等于 nums.length 时 并且  刚好rest ==0
		 * 的 话 这样 的 话 不 就 结果 就不对 对吧 
		 */
		if(index == nums.length) {
			return 0;
		}
		int ways = 0;
		/**
		 * 对 数组 进行 排序  可以  做到   剪枝 和  去重   两种效果
		 *                                    这里   有 剪枝   
		 */
		for(int i = index ;i < nums.length && rest - nums[i] >= 0;i++) {
			if(i > index && nums[i] == nums[i-1]) {
				continue;
			}
			/**
			 * 			if(i > 0 && nums[i] == nums[i-1]) {
				         continue;
		               	}
			 * 这种 去重的 方式 是错的    画个 多叉树的  图 就明白 了 
			 * 多叉树 的  演示  很清晰的 一看就明白了
			 * 
			 */
			ways += processTwo(nums,rest - nums[i],i + 1);
		}
		return ways;
	}
	public static int dpTwo(int arr[],int target) {
		int len  = arr.length;
		int  dp [][] = new int [len + 1][target + 1];
//		dp[len][0] = 1;
		/**
		 * 这里 解释 一下为啥 这里 的  index =len 而不是 n -1
		 * 注意 看第三层 for循环 这里  当 index 为 len 
		 * 第三层 for  压根 就不会 执行 那为什么 还要  等于 len
		 * 而不是 从 len - 1 开始   
		 * for(int i = index ;i < len && rest - arr[i] >= 0; i++)
		 * 
		 * 其实关键的 点  核心 代码 就是  为了  dp[len][0] =1
		 * 注意 看下面的 代码   当 i = len -1  的 时候 
		 * ways += dp[i + 1][rest - arr[i]];
		 * dp[i+1][rest - arr[i]] 不就是 dp[len][rest - arr[i]] 
		 * 
		 * 只要 理解 了 这些 那就  容易
		 * 所以 可以 直接  写 index = len -1
		 * 但是 必须 在  填写 缓存表 之前 把 dp [len][0] = 1; 设置上对吧 
		 * 这不就 全 明白了嘛 
		 */
		for(int  index = len ; index >= 0;index -- ) {
			dp[index][0] = 1;
			for(int rest = 1; rest <= target;rest++) {
				int ways = 0;
				for(int i = index ;i < len && rest - arr[i] >= 0; i++) {
					if(i > index && arr[i] == arr[i - 1]) {
						continue;
					}
					ways += dp[i + 1][rest - arr[i]];
				}
				dp[index][rest] = ways;
			}
		}
		return dp[0][target];
	}
/**
	
	写不出来  这个  去重版本 的 最终 优化 版的  动态规划
	
	还是等 背包 问题 解决 之后  再 来 好好的思考一下 怎么优化 这道题
	
	
	先测试 一下  没有 重复 元素的  版本 (不用去重)
	 
*/
	public static int dpTwoFinall(int arr[],int target) {
		int len = arr.length;
		int dp [][] = new int [len + 1][target + 1];
		/**
		 * 
		 * 这句 代码 很  重要的   
		 * 至于 原理 上面的 注释 已经  解释 
		 *dp[len][0] = 1; 
		 *  * 这里 解释 一下为啥 这里 的  index =len 而不是 n -1
		 * 注意 看第三层 for循环 这里  当 index 为 len 
		 * 第三层 for  压根 就不会 执行 那为什么 还要  等于 len
		 * 而不是 从 len - 1 开始   
		 * for(int i = index ;i < len && rest - arr[i] >= 0; i++)
		 * 
		 * 其实关键的 点  核心 代码 就是  为了  dp[len][0] =1
		 * 注意 看下面的 代码   当 i = len -1  的 时候 
		 * ways += dp[i + 1][rest - arr[i]];
		 * dp[i+1][rest - arr[i]] 不就是 dp[len][rest - arr[i]] 
		 * 
		 * 只要 理解 了 这些 那就  容易
		 * 所以 可以 直接  写 index = len -1
		 * 但是 必须 在  填写 缓存表 之前 把 dp [len][0] = 1; 设置上对吧 
		 * 这不就 全 明白了嘛 
		 */
		dp[len][0] = 1;
		for(int index = len - 1;index >= 0; index--) {
			dp[index][0] = 1;
//			if(index > 0 && arr[index] == arr[index - 1]) {
//				continue;
//			}
			for(int rest = 1;rest <= target;rest++) {
//				if(index > 0 && arr[index] == arr[index - 1]) {
//					continue;
//				}
				dp[index][rest] = dp[index+1][rest];
				if(rest - arr[index] >= 0) {
					dp[index][rest] += dp[index + 1][rest - arr[index]]; 
				}
			}
		}
		return dp[0][target];
	}
	/**
	  这里  结合       <射箭比赛的最大得分问题> 去说明 一下 这个问题
	 * 就是 数组 无序的  情况 怎么 去写 这个  逻辑
	 * 注意一下  下面的 代码  rest - nums[i] > 0 这里 进行 剪枝 
	 * 而剪枝  的 前提 就是  对 数组   nums   进行排序才可以 这样 写  
	     for(int i = index ;i < nums.length && rest - nums[i] >= 0;i++) {
		  ways += processTwo(nums,rest - nums[i],i + 1);
	     }
	    
	     但是  如果 题目 中 条件  或者   解答 题目的 过程 中 发现   无法  通过 对数组 排序 而解决 
	    比如 <射箭问题 中的最大得分 >
	    正确 结果 时 对 数组 的 下标 索引 进行 操作 (求和 )
	    那么 排序 后 原先  i 下标  对应的 value 就已经 变了 答案 肯定 是错的   
	    那就 无法 进行 剪枝  操作   那就 直接 算呗
	     那么 对于 该题        <组合 求和>  进行 不剪枝 的操作 示范 
	 * 
	 */
	public static int processUpdate(int nums[],int rest,int index) { 
		if(rest == 0){
			return 1;
		}

		if(index == nums.length) {
			return 0;
		}
		int ways = 0;

		for(int i = index ;i < nums.length;i++) {
			if(rest - nums[i] >= 0) {
				ways += processUpdate(nums,rest - nums[i],i + 1);				
			}
//			else {
//				ways += processUpdate(nums,rest,i + 1);
//			}
		}
		return ways;
	}
}
